#pragma once
#include<iostream>
#include<cmath>
#include<queue>
#include<string>
#include<math.h>
#include<assert.h>
#include<stack>
#include<vector>
#include<unordered_map>
using namespace std;
enum color
{
    black,
    red
};
template<class T>//T代表的是节点的类型，节点的类型可能是key-value，也可能是key的类型，k代表的是key的类型
class rbtreenode
{
public:
    typedef rbtreenode<T> node;
    color _color;
    T _data;
    node* _left;
    node* _right;
    node* _parent;
    rbtreenode(const T& data) :
        _left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _data(data)
    {}
};

template<class T,class ref,class ptr>
struct rbtreeiterator//红黑树的迭代器结构体
{
    typedef rbtreenode<T> node;
    node* _node;
    node* _root;
    rbtreeiterator(node* nd,node* root) :
        _node(nd),
        _root(root)
    {}
    ref operator*()
    {
        return _node->_data;
    }
    ptr operator->()
    {
        return &(_node->_data);
    }
    rbtreeiterator& operator++()
    {
        if (_node->_right != nullptr)
        {
            _node = _node->_right;
            while (_node->_left) _node = _node->_left;
        }
        else
        {
            node* parent = _node->_parent;
            while (parent)
            {
                if (_node == parent->_left) break;
                else
                {
                    _node = parent;
                    parent = parent->_parent;
                }
            }
            _node = parent;
        }
        return *this;
    }
    rbtreeiterator& operator--()
    {
        if (_node == nullptr)
        {
            if (_root == nullptr) return *this;
            _node = _root;
            while (_node->_right) _node = _node->_right;
        }
        else
        {
            if (_node->_left)
            {
                _node = _node->_left;
                while (_node->_right) _node = _node->_right;
            }
            else
            {
                node* parent = _node->_parent;
                while (parent && parent->_left == _node)
                {
                    _node = parent;
                    parent = parent->_parent;
                }
                _node = parent;
            }
        }
        return *this;
    }
    bool operator!=(const rbtreeiterator& other)
    {
        if (this->_node != other._node)
            return true;
        else return false;
    }
    bool operator==(const rbtreeiterator& other)
    {
        if (this->_node != other._node)
            return false;
        else return true;
    }
};
//迭代器本事是一个封装了指针的结构体，迭起器一定是跟指针脱不了干系的。之所以将指针封装起来就是因为指针的++是数值上的+1而不是我们想要的容器指针位置的改变
//所以迭代器就一定需要将一些符号重载。然后在容器类中我们只需要实现知道迭代器的begin和end即可。
template<class k, class T,class keyoft>//keyoft是一个仿函数
class rbtree
{
public:
    typedef rbtreenode<T> node;
    typedef rbtreeiterator<T,T&,T*> Iterator;
    typedef rbtreeiterator<T, const T&, const T*> const_Iterator;
    Iterator begin()
    {
        node* pcur = _root;
        while (pcur && pcur->_left)
            pcur = pcur->_left;
        return Iterator(pcur,_root);
    }
    Iterator end()
    {
        return Iterator(nullptr,_root);
    }
    const_Iterator begin() const 
    {
        node* pcur = _root;
        while (pcur && pcur->_left)
            pcur = pcur->_left;
        return const_Iterator(pcur, _root);
    }
    const_Iterator end() const 
    {
        return const_Iterator(nullptr, _root);
    }
    pair<Iterator, bool> insert(const T& data)
    {
        node* newnode = new node(data);
        newnode->_color = red;
        if (_root == nullptr)
        {
            _root = newnode;
            _root->_color = black;
            return { Iterator(_root,_root),true };
        }
        node* parent = nullptr;
        node* cur = _root;
        keyoft kot;
        while (cur)
        {
            if (kot(cur->_data) > kot(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else return { Iterator(cur,_root),false };
        }
        if (kot(parent->_data) > kot(data))
            parent->_left = newnode;
        else
            parent->_right = newnode;
        cur = newnode;
        newnode->_parent = parent;
        while (parent && parent->_color == red)
        {
            node* g = parent->_parent;
            node* u = g->_left == parent ? g->_right : g->_left;
            if (u && u->_color == red)
            {
                g->_color = red;
                u->_color = black;
                parent->_color = black;

                newnode = g;
                parent = g->_parent;
            }
            else
            {
                if (parent == g->_left)
                {
                    if (newnode == parent->_left) // LL
                    {
                        RotateR(g);
                        parent->_color = black;
                        g->_color = red;
                    }
                    else // LR
                    {
                        RotateLR(g);
                        newnode->_color = black;
                        g->_color = red;
                    }
                }
                else
                {
                    if (newnode == parent->_right) // RR
                    {
                        RotateL(g);
                        parent->_color = black;
                        g->_color = red;
                    }
                    else // RL
                    {
                        RotateRL(g);
                        newnode->_color = black;
                        g->_color = red;
                    }
                }
                break;
            }
        }
        _root->_color = black; // 确保根为黑
        return { Iterator(cur,_root),true };
    }
    Iterator find(const k& key)
    {
        keyoft kot;
        node* cur = _root;
        while (cur)
        {
            if (kot(cur) == key) return Iterator(cur, _root);
            else if (kot(cur) < key) cur = cur->_right;
            else cur = cur->_left;
        }
        return Iterator(nullptr, _root);
    }
private:
    keyoft kot;//这个是仿函数的实例化出来的对象，这个对象可以当最函数名使用
    node* _root = nullptr;
    void RotateR(node* parent)
    {
        node* subL = parent->_left;
        node* subLR = subL->_right;

        subL->_right = parent;//先改变subL相应的指针
        subL->_parent = parent->_parent;

        if (parent == _root) _root = subL;
        else
        {
            if (parent->_parent->_left == parent)//改parent->_parent得到指针
                parent->_parent->_left = subL;
            else parent->_parent->_right = subL;
        }

        parent->_parent = subL;//再改parent相应的指针
        parent->_left = subLR;

        if (subLR) subLR->_parent = parent;//修改subLR的指针
    }
    void RotateL(node* parent)
    {
        node* subR = parent->_right;
        node* subRL = subR->_left;

        //修改subR的相关指针
        subR->_parent = parent->_parent;
        subR->_left = parent;

        if (parent == _root) _root = subR;
        else
        {
            if (parent->_parent->_left == parent)
                parent->_parent->_left = subR;
            else parent->_parent->_right = subR;
        }

        if (subRL) subRL->_parent = parent;//修改subRL的相关指针

        parent->_right = subRL;//修改parent相应的指针
        parent->_parent = subR;//注意这里修改了parent的parent，因为原parent的parent也有指针需要修改，所以要么用变量记录一下，要么将paarent的parent的修改放到后面
    }
    void RotateLR(node* parent)
    {
        node* subl = parent->_left;
        node* sublr = subl->_right;
        RotateL(subl);
        RotateR(parent);
    }
    void RotateRL(node* parent)
    {
        node* subr = parent->_right;
        node* subrl = subr->_left;
        RotateR(subr);
        RotateL(parent);
    }
};

